package org.leetcode.middle.leetcode139;

import java.util.HashSet;
import java.util.List;

public class Solution2 {
    public boolean wordBreak(String s, List<String> wordDict) {

        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        HashSet<String> set = new HashSet<>();
        for (String str : wordDict) {
            set.add(str);
        }

        for (int i = 1; i <= n; i++) {
            for (String str:set) {
                int size=str.length();
                if (i>=size && dp[i-size]){
                    String substring = s.substring(i - size, i);
                    if (substring.equals(str)){
                        dp[i]=true;
                        break;
                    }
                }
            }
        }

        return dp[n];
    }
}
